/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util.iterators;

import java.util.Arrays;
import java.util.NoSuchElementException;

/** Iterator that enumerates all instances of a given abelian pattern
 *  in lexicographical order, i.e. all strings that match the given 
 *  abelian pattern. */
public class AbelianPatternInstanceIterator implements LexicographicalIterator {
	int length;
	/** Contains a list of characters that are to be placed
	 *  in the remaining part of the string. */
	int[][] remainingCharacters;
	/** Frequencies of the remaining character as given in 
	 *  remainingCharacters. */
	int[][] remainingFrequencies;
	/** Current position in array remainingCharacters,
	 *  i.e. current[i]=remainingCharacters[i][currentPositions[i]] */
	int[] currentPositions;
	/** Current string (instance of abelian pattern) */
	int[] current;
	int currentLeftmostChangedPos;
	int lastLeftmostChangedPos;
	
	public AbelianPatternInstanceIterator(int[] frequencies) {
		length=0;
		int n = 0;
		for (int i : frequencies) {
			length+=i;
			if (i>0) ++n;
		}
		current = new int[length];
		currentPositions = new int[length];
		for (int i=0; i<length; ++i) currentPositions[i]=-1;
		remainingCharacters = new int[length][];
		remainingFrequencies = new int[length][];
		remainingCharacters[0] = new int[n];
		remainingFrequencies[0] = new int[n];
		n=0;
		for (int i=0; i<frequencies.length; ++i) {
			if (frequencies[i]>0) {
				remainingCharacters[0][n]=i;
				remainingFrequencies[0][n]=frequencies[i];
				++n;
			}
		}
		for (int i=0; i<length; ++i) {
			if (!step(i)) {
				current=null;
				return;
			}
		}
		currentLeftmostChangedPos=0;
		lastLeftmostChangedPos=-1;
	}
	
	/** Increases character at position. Returns false if there are
	 *  no characters left for this position (end of enumeration).
	 */
	private boolean step(int position) {
		int j = ++currentPositions[position];
		if (j<remainingCharacters[position].length) {
			current[position]=remainingCharacters[position][j];
			// compute remaining characters of next position
			if (position+1<length) {
				if (remainingFrequencies[position][j]==1) {
					int n = remainingCharacters[position].length - 1;
					remainingCharacters[position+1] = new int[n];
					remainingFrequencies[position+1] = new int[n];
					System.arraycopy(remainingCharacters[position], 0, remainingCharacters[position+1], 0, j);
					System.arraycopy(remainingFrequencies[position], 0, remainingFrequencies[position+1], 0, j);
					System.arraycopy(remainingCharacters[position],j+1, remainingCharacters[position+1], j, n-j);
					System.arraycopy(remainingFrequencies[position],j+1, remainingFrequencies[position+1], j, n-j);
				} else {
					int n = remainingCharacters[position].length;
					remainingCharacters[position+1] = new int[n];
					remainingFrequencies[position+1] = new int[n];
					System.arraycopy(remainingCharacters[position], 0, remainingCharacters[position+1], 0, n);
					System.arraycopy(remainingFrequencies[position], 0, remainingFrequencies[position+1], 0, n);
					remainingFrequencies[position+1][j]-=1;
				}
				currentPositions[position+1]=-1;
			}
			return true;
		} else {
			currentPositions[position]=-1;
			return false;
		}
	}
	
	public boolean hasNext() {
		return current!=null;
	}

	public int[] next() {
		if (current==null) throw new NoSuchElementException();
		int[] result = Arrays.copyOf(current, length);
		lastLeftmostChangedPos=currentLeftmostChangedPos;
		int pos = length-1;
		for (;pos>=0;--pos) {
			if (step(pos)) break;
		}
		currentLeftmostChangedPos=pos;
		if (pos<0) {
			current=null;
		} else {
			++pos;
			for (;pos<length;++pos) {
				step(pos);
			}
		}
		return result;
	}

	public int[] peek() {
		return Arrays.copyOf(current, current.length);
	}
	
	/** Advance to next character at given position, that means a subsequent call
	 *  to next() will return the next string in lexicographical order, such that
	 *  leftmostChangedPosition<=position. */
	public void skip(int position) {
		if (current==null) return;
		if (currentLeftmostChangedPos<=position) return;
		for (;position>=0;--position) {
			if (step(position)) break;
		}
		currentLeftmostChangedPos=position;
		if (position<0) {
			current=null;
		} else {
			++position;
			for (;position<length;++position) {
				step(position);
			}
		}
	}
	
	/** Returns the leftmost position that changed when the last returned
	 *  string was generated. */
	public int getLeftmostChangedPosition() {
		return lastLeftmostChangedPos;
	}
	
	public void remove() {
		throw new UnsupportedOperationException();
	}

	@Override
	public int getStringLength() {
		return length;
	}

}
